package com.leetcode.图;

import org.junit.Test;

import java.util.*;

/**
 * @author lzf
 * @date 2023/10/24
 * LeetCode 2316 统计无向图中无法互相到达点对数
 * 题目描述：
 * 给你一个整数 n ，表示一张 无向图 中有 n 个节点，编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。
 * 请你返回 无法互相到达 的不同 点对数目 。
 * 例1：
 * 输入：n = 3, edges = [[0,1],[0,2],[1,2]]
 * 输出：0
 * 解释：所有点都能互相到达，意味着没有点对无法互相到达，所以我们返回 0 。
 * 例2：
 * 输入：n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
 * 输出：14
 * 解释：总共有 14 个点对互相无法到达：
 * [[0,1],[0,3],[0,6],[1,2],[1,3],[1,4],[1,5],[2,3],[2,6],[3,4],[3,5],[3,6],[4,6],[5,6]]
 * 所以我们返回 14 。
 *
 * 输入约束：
 * 1 <= n <= 105
 * 0 <= edges.length <= 2 * 105
 * edges[i].length == 2
 * 0 <= ai, bi < n
 * ai != bi
 * 不会有重复边。
 */
public class L2316 {
    /**
     * 解题思路（自己的做法，参考知识点：并查集）
     * [0,2] 表示节点0和节点2有一边，现在将所有能够互相抵达的节点称之为“长边”，即[0,2],[0,5]原本表示两条边，
     * 但现在节点0能够抵达节点5，因此节点0、2、5称为“长边”
     * 如果整个图中，只有两条“长边”，例如，a:[0, 2, 5]和b:[1, 3, 4]，那么“长边”a的节点都无法抵达长边b的节点，因此，
     * 题目结果（无法互相到达点对数）应该为a和b的节点数的相乘，即为9。
     * 因此，题目转换为，寻找图中的所有“长边”，结果就是所有“长边”的节点数两两相乘的总和。
     * 解决方法1：
     * 用一个集合来存储“长边”，List或Set，每次添加一条边，都需要检查所有集合，并且还需要进行合并操作。
     * 如：目前有List1:[0, 2]和List2:[3, 5]两条“长边”，现在加入第三条边[2, 3]，则整体应该是一条长边[0, 2, 3, 5]，就需要合并List1和List2。
     * 这种做法，1是空间复杂度大，因为会用到很多集合，2是合并集合不好操作，需要进行很多判断，3是如果合并集合的算法写不好，也会导致时间复杂度大大提升。
     * 解决方法2：参考并查集的知识点
     * 存储每一条“长边”的头节点，因为题目的节点是0到n - 1，因此，头节点可以取最小的节点。
     * 如果两个节点的头节点相同，则表示两个节点在同一条“长边”中，因此这两个节点可以互相抵达。
     * 用一个数组head存储，head[i]表示：节点i的头节点为head[i]
     * 例如“长边”[0, 2, 3, 5]可以表示为：head:[0, 1, 0, 0, 4, 0]，这里下标为0, 2, 3, 5的值都为0，表示，节点0、2、3、5的头节点都为节点0。
     * 一开始并不能马上确定一个节点的头节点是什么，例如head:[0, 1, 2]，添加边[1, 2]，更新head:[0, 1, 1]。添加边[0, 1]，更新head:[0, 0, 1]
     * 可以发现，节点2的头节点为1，但是经过后面的更新，节点1的头节点为节点0，那节点2的头节点应该也要更新为节点0，因此，
     * 每添加一条边，都要进行一个head的更新，并且所有的边添加完成之后，再次更新head所有节点的头节点。
     * 最后，统计head，如值为0的节点有5个，表示其中一条“长边”的节点为5。
     */

    public long countPairs(int n, int[][] edges) {
        // 初始化head数组
        int[] head = new int[n];
        for (int i = 0; i < n; i++) {
            // 所有节点的头节点均为本身，表示自己是独立的一条“长边”
            head[i] = i;
        }
        for (int[] edge : edges) {
            // edge[0]、edge[1]表示两个节点
            int rootMin = Math.min(head[edge[0]], head[edge[1]]);
            int nodeMin = Math.min(edge[0], edge[1]);
            int min = Math.min(rootMin, nodeMin);
            updateNode(head, edge[0], min);
            updateNode(head, edge[1], min);
        }
        // key:头节点，value:相同头节点的个数
        Map<Integer, Integer> roots = new HashMap<>();
        for (int i = 0; i < n; i++) {
            roots.compute(findAndUpdate(head, i), (k, v) -> v != null ? v + 1 : 1);
        }
//        System.out.println(Arrays.toString(head));
//        System.out.println(roots);
        long result = 0;
        List<Integer> list = new ArrayList<>(roots.values());
        // 用传统的两成for循环计算两两相乘的总和，时间复杂度是(o^2)，不行！
        // 可以先计算每个值跟其他值的总和相乘的结果，因为会重复计算，因此结果除以2即可。
        int totalSum = list.stream().mapToInt(Integer::intValue).sum();
        for (Integer i : list) {
            result += (long) i * (totalSum - i);
        }
        return result / 2;
    }

    /**
     * 查找并更新节点i的头节点
     * @param head
     * @param i
     * @return
     */
    int findAndUpdate(int[] head, int i) {
        if (head[i] == i) {
            return i;
        } else {
            head[i] = findAndUpdate(head, head[i]);
            return head[i];
        }
    }

    /**
     * 更新head数组，递归更新node的头节点
     * 例如：节点3的头节点是节点2，如果添加[0, 3]则需要更新节点3的头节点为0，并且还需要更新节点2的头节点也为0
     * @param head  head数组
     * @param node  当前节点
     * @param min   最新的头节点
     */
    void updateNode(int[] head, int node, int min) {
        // 当前节点的头节点比最新的头节点还小，则不需要更新
        if (head[node] > min) {
            // 当头节点是本身时也不需要更新
            if (head[node] != node) {
                updateNode(head, head[node], min);
            }
            head[node] = min;
        }
    }

    @Test
    public void test() {
//        int[][] edges = new int[][]{{0, 2}, {0, 5}, {2, 4}, {1, 6}, {5, 4}}; // n = 7
//        int[][] edges = new int[][]{{5, 0}, {1, 0}, {10, 7}, {9, 8}, {7, 2}, {1, 3}, {0, 2}, {8, 5}, {4, 6}, {4, 2}}; // n = 11
//        int[][] edges = new int[][]{{15, 0}, {1, 14}, {2, 11}, {4, 3}, {5, 15}, {8, 2}, {14, 12}}; // n = 16
        int[][] edges = new int[][]{{3, 2}, {1, 2}, {3, 0}}; // n = 4
        System.out.println(countPairs(4, edges));
    }
}
